import random
import time
class sort:
    def __init__(self,n):
        self.len = n
        self.arr = [0] * n
        self.data_random()
    def data_random(self):
        for i in range(self.len):
            self.arr[i] = random.randint(0,100)
    def quilk_sort(self,left,right):
        if(left < right):
            pivot = self.patition(left,right)
            self.quilk_sort(left,pivot-1)
            self.quilk_sort(pivot+1,right)
    def patition(self,left,right):
        k=i=left;
        arr = self.arr
        for i in range(left,right):
            if(arr[i] < arr[right]):
                arr[i],arr[k] = arr[k],arr[i]
                k+=1
        arr[k],arr[right] = arr[right],arr[k]
        return k
    def adjust_max_heap(self, pos, arr_len):
        """
        把某个子树调整为大根堆
        :param pos: 被调整的元素位置，是父亲
        :param arr_len: 当时列表总长度
        :return:
        """
        arr = self.arr
        dad = pos
        son = 2 * dad + 1
        while son < arr_len:  # 左孩子小于列表长度
            if son + 1 < arr_len and arr[son] < arr[son + 1]:  # 判断右孩子存在，且右孩子大于左孩子
                son += 1
            if arr[son] > arr[dad]:
                arr[dad], arr[son] = arr[son], arr[dad]
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap_sort(self):
        # 把列表调整为大根堆
        for parent in range(self.len // 2 - 1, -1, -1):
            self.adjust_max_heap(parent, self.len)
        arr = self.arr
        arr[0], arr[self.len - 1] = arr[self.len - 1], arr[0]  # 堆顶元素和最后一个元素交换
        for arr_len in range(self.len - 1, 1, -1):
            self.adjust_max_heap(0, arr_len)
            arr[0], arr[arr_len - 1] = arr[arr_len - 1], arr[0]

    def test_time_use(self, sort_func, *args, **kwargs):
        """
        回调函数
        :param sort_func:
        :param args:
        :param kwargs:
        :return:
        """
        start = time.time()
        sort_func(*args, **kwargs)
        end = time.time()
        print(f'总计用时{end - start}')


if __name__ == '__main__':
    my_sot = sort(10)
    print(my_sot.arr)
    my_sot.quilk_sort(0,9)
    print(my_sot.arr)